package org.example.leetcode.interview.slide;

public class LC0005 {
    /**
     * 构造一个滑窗, 检测滑窗内的字符串是否是回文串
     * 滑窗左侧从0开始不变, 右侧从最大长度不断减少(第一层循环), 同时滑窗向右推进验证是否回文
     * 第一圈: l                r
     * 第二圈: l               r
     *         l               r (滑窗整体右移了)
     * 第三圈: l              r
     *         l              r
     *          l              r
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        for (int len = chars.length; len > 1; len--) {
            int left = 0;
            int right = left + len - 1;
            // len会变, 这里需要取数组的长度
            while (right < chars.length) {
                if (isPalindrome(chars, left, right)) {
                    // substring左闭右开, 回文判断是左闭右闭, 所以需要right + 1
                    return s.substring(left, right + 1);
                }
                left++;
                right++;
            }
        }

        return s.substring(0, 1);
    }

    private boolean isPalindrome(char[] chars, int left, int right) {
        while (left < right) {
            if (chars[left++] != chars[right--]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        LC0005 solu = new LC0005();
        solu.longestPalindrome("babad");
        solu.longestPalindrome("cbbd");
    }
}
